package com.lry.basic.algorithm.dp;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/6/26
 */
//        Input: "(()"
//        Output: 2
//        Explanation: The longest valid parentheses substring is "()"

//        Input: ")()())"
//        Output: 4
//        Explanation: The longest valid parentheses substring is "()()"

public class LongestValidParentheses {

    public static void main(String[] args) {
        System.out.println(longestValidParentheses(")()())"));
    }

    public static int longestValidParentheses(String s){
        if(null==s||s.length()==0||s.length()==1)return 0;
        LinkedList<Integer> stack = new LinkedList<Integer>();
        int start=-1,max=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                stack.push(i);
            }else{
                if(!stack.isEmpty()){
                    stack.pop();
                    if(!stack.isEmpty()){
                        max = Math.max(max,i-stack.peek());
                    }else{
                        max = Math.max(max,i-start);
                    }
                }else{
                    start=i;
                }
            }
        }
        return max;
    }
}
